Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 23 Issue 6
November  2008
Turn off MathJax
Article Contents
Abstract
References
Nan Chen, Li-Dan Shou, Gang Chen, Jin-Xiang Dong. Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies[J]. Journal of Computer Science and Technology, 2008, 23(6): 998-1014.
Citation: Nan Chen, Li-Dan Shou, Gang Chen, Jin-Xiang Dong. Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies[J]. Journal of Computer Science and Technology, 2008, 23(6): 998-1014.
shu

Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies

  • College of Computer Science, Zhejiang University, Hangzhou 310027, China

More Information
  • Received Date: June 26, 2007
  • Revised Date: May 12, 2008
  • Published Date: November 09, 2008
    Abstract
  • In recent years, management of moving objects has emerged as anactive topic of spatial access methods. Various data structures(indexes) have been proposed to handle queries of moving points, forexample, the well-known Bx-tree uses a novel mapping mechanism toreduce the index update costs. However, almost all the existingindexes for predictive queries are not applicable in certaincircumstances when the update frequencies of moving objects becomehighly variable and when the system needs to balance the performanceof updates and queries. In this paper, we introduce two kinds ofnovel indexes, named By-tree and \alBy-tree. By associatinga {\em prediction life period} with every moving object, the proposedindexes are applicable in the environments with highly variableupdate frequencies. In addition, the \alBy-tree can balance theperformance of updates and queries depending on a balance parameter.Experimental results show that the By-tree and \alBy-treeoutperform the Bx-tree in various conditions.
    • FullText(HTML)
    • References (17)
  • [1] Christian S Jensen, Dalia Tiesyte, Nerius Tradisauskas. Robust B+-tree-based indexing of moving objects. In {\it Proc. MDM}, Nara, Japan, 2006, p.12.
    [2]
    } Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In {\it Proc. SIGMOD Conference}, Boston, MA, USA, 1984, pp.47--57.
    [3]
    } Simonas Saltenis, Christian S Jensen, Scott T Leutenegger, Mario A Lopez. Indexing the positions of continuously moving objects. In {\it Proc. SIGMOD Conference}, Dallas, TX, USA, 2000, pp.331--342.
    [4]
    } Simonas Saltenis, Christian S Jensen. Indexing of moving objects for location-based services. In {\it Proc. ICDE}, San Jose, CA, USA, 2002, pp.463--472.
    [5]
    } Yufei Tao, Dimitris Papadias, Jimeng Sun. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In {\it Proc. VLDB}, Berlin, Germany, 2003, pp.790--801.
    [6]
    } Jignesh M Patel, Yun Chen, V Prasad Chakka. STRIPES: An efficient index for predicted trajectories. In {\it Proc. SIGMOD Conference}, Paris, France, 2004, pp.637--646.
    [7]
    } Hanan Samet. The quadtree and related hierarchical data structures. {\it ACM Comput. Surv}., 1984, 16(2): 187--260.
    [8]
    } Christian S Jensen, Dan Lin, Beng Chin Ooi. Query and update efficient B+-tree based indexing of moving objects. In {\it Proc. VLDB}, Toronto, Ontario, Canada, 2004, pp.768--779.
    [9]
    } Mohamed F Mokbel, Thanaa M Ghanem, Walid G Aref. Spatio-temporal access methods. {\it IEEE Data Eng. Bull}., 2003, 26(2): 40--49.
    [10]
    } Bin Lin, Hoda Mokhtar, Rafael Pelaez-Aguilera, Jianwen Su. Querying moving objects with uncertainty. In {\it Proc. Vehicular Technology Conference}, Orlando, FL, USA, 2003, pp.2783--2787.
    [11]
    } Ji-Dong Chen, Xiao-Feng Meng. Indexing future trajectories of moving objects in a constrained network. {\it Journal of Computer Science and Technology}, 2007, 22(2): 245--251.
    [12]
    } Yufei Tao, Jun Zhang, Dimitris Papadias, Nikos Mamoulis. An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces. {\it IEEE Trans. Knowl. Data Eng}., 2004, 16(10): 1169--1184.
    [13]
    } Mong-Li Lee, Wynne Hsu, Christian S. Jensen, Bin Cui, Keng Lik Teo. Supporting frequent updates in R-trees: A bottom-up approach. In {\it Proc. VLDB}, Berlin, Germany, 2003, pp.608--619.
    [14]
    } Xiaopeng Xiong, Walid G Aref. R-trees with update memos. In {\it Proc. ICDE}, Atlanta, Georgia, USA, 2006, p.22.
    [15]
    } Goetz Graefe. B-tree indexes for high update rates. {\it SIGMOD Record}, 2006, 35(1): 39--44.
    [16]
    } Bongki Moon, H V Jagadish, Christos Faloutsos, Joel H Saltz. Analysis of the clustering properties of the Hilbert space-filling curve. {\it IEEE Trans. Knowl. Data Eng}., 2001, 13(1): 124--141.
    [17]
    } V Srinivasan, Michael J Carey. Performance of B-tree concurrency algorithms. In {\it Proc. SIGMOD Conference}, Denver, CO, USA, 1991, pp.416--425.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (16) PDF downloads (1560) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return